#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=problem-list-v2&envId=z8Em6vKo
// 17. 电话号码的字母组合

class Solution
{
private:
    unordered_map<char, string> recordNumOfChar;

public:
    void recursionTry(vector<string> &ans, string digits, string curStr, int begin)
    {
        if(begin == digits.size()){
            ans.push_back(curStr);
            return;
        }
        for(char ch : recordNumOfChar[digits[begin]]){
            curStr += ch;
            recursionTry(ans, digits, curStr, begin + 1);
            curStr.pop_back();
        }
    }
    vector<string> letterCombinations(string digits)
    {
        if(digits.size() == 0){
            return {};
        }
        recordNumOfChar['2'] = "abc";
        recordNumOfChar['3'] = "def";
        recordNumOfChar['4'] = "ghi";
        recordNumOfChar['5'] = "jkl";
        recordNumOfChar['6'] = "mno";
        recordNumOfChar['7'] = "pqrs";
        recordNumOfChar['8'] = "tuv";
        recordNumOfChar['9'] = "wxyz";

        vector<string> ans;
        string curString;
        recursionTry(ans, digits, curString, 0);
        return ans;
    }
};

int main()
{
    return 0;
}